package org.sselab.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author pinker on 2017/11/23
 */
public class RandomList {
  Map<Integer, RandomListNode> map = new HashMap<>();
  int index;

  public RandomListNode copyRandomList(RandomListNode head) {
//    return method1(head);
    return method2(head);
  }

  private RandomListNode method2(RandomListNode head) {

    return null;
  }

  private RandomListNode method1(RandomListNode head) {
    RandomListNode root = copyList(head);
    setRandomNode(root, head);
    return root;
  }

  private RandomListNode copyList(RandomListNode head) {
    if (head == null) {
      return null;
    }
    RandomListNode root = new RandomListNode(head.label);
    map.put(++index, root);
    root.next = copyList(head.next);
    return root;
  }

  private void setRandomNode(RandomListNode copy, RandomListNode source) {
    RandomListNode root = source;
    while (source != null) {
      if (source.random == null) {
        copy.random = null;
      } else {
        int index = findIndex(source.random, root);
        copy.random = map.get(index);
      }
      source = source.next;
      copy = copy.next;
    }
  }

  public int findIndex(RandomListNode random, RandomListNode root) {
    int index = 1;
    while (root != null) {
      if (root == random) {
        break;
      }
      index++;
      root = root.next;
    }
    return index;
  }
}

class RandomListNode {
  int label;
  RandomListNode next, random;

  RandomListNode(int x) {
    this.label = x;
  }
};
